package org.example.myleet.rosalind.scsp;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.findSuperSequence("ATCTGAT", "TGCATA");
        solution.findSuperSequence("AGGAGACCCAGGTGAGGTGCATAAGCTAGAAGTTCCCACCGGATACTGCTGCACTATCTCCACGTTTCAACACATTCTCCTTTCCG", "AGTGTATCCTGAGCGCATATATAACCGTCATGCAATGTTGTAGAACAATCACGGCGGCATCGGCTAAAGAGGATCGTGCGCGACCAT");
    }

    /**
     * 原理：由于supersequence（超序列）是s和t的字符重合最多的序列，才能使得超序列最短
     * 先求出s和t的LCSQ，这样s和t的字符重合最多的最长公共子序列就有了，然后是将s和t中未匹配LCSQ的字符按顺序补上就行了
     */
    public void findSuperSequence(String s, String t) {
        //先求最长公共子序列
        String lcsq = findLongestCommonSubsequence(s, t);
        StringBuilder res = new StringBuilder();
        //m和n分别是s和t的游标
        int m = 0, n = 0;
        for (int i = 0; i < lcsq.length(); ++i) {
            char c = lcsq.charAt(i);
            char cs = s.charAt(m);
            char ct = t.charAt(n);
            while (cs != c) {
                //补充s的字符直到遇上公共子序列的字符
                res.append(cs);
                ++m;
                cs = s.charAt(m);
            }
            ++m;
            while (ct != c) {
                //补充t的字符直到遇上公共子序列的字符
                res.append(ct);
                ++n;
                ct = t.charAt(n);
            }
            ++n;
            res.append(c);
        }
        //如果s和t还有未补充完的字符，继续补充
        while (m < s.length()) {
            res.append(s.charAt(m++));
        }
        while (n < t.length()) {
            res.append(t.charAt(n++));
        }
        System.out.println(res);
    }

    public String findLongestCommonSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); ++i) {
            dp[i][0] = 0;
        }
        for (int j = 0; j < t.length(); ++j) {
            dp[0][j] = 0;
        }
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j < t.length(); ++j) {
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                int elongation = s.charAt(i) == t.charAt(j) ? 1 : 0;
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + elongation);
            }
        }
        StringBuilder res = new StringBuilder();
        int i = s.length(), j = t.length();
        while (i > 0 && j > 0) {
            if (dp[i][j] > dp[i - 1][j - 1] && dp[i][j] > dp[i - 1][j] && dp[i][j] > dp[i][j - 1]) {
                --i;
                --j;
                res.append(s.charAt(i));
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                --i;
            } else {
                --j;
            }
        }
        res.reverse();
        return res.toString();
    }
}
